namespace Aurora
{
    template<class K,class V>
    struct AVLTreeNode
    {
        pair<K,V> _kv;
        AVLTreeNode<K,V>* _left;
        AVLTreeNode<K,V>* _right;
        AVLTreeNode<K,V>* _parent;
        int bf;
        AVLTreeNode(const pair<K,V>& kv)
            :_kv(kv)
            ,_left(nullptr)
            ,_right(nullptr)
            ,_parent(nullptr)
            ,bf(0)
        {}
    };
    template<class K,class V>
    class AVLTree
    {
        using Node = AVLTreeNode<K,V>;
    public:
        bool Insert(const pair<K,V>& kv)
        {
            if(_root == nullptr)
            {
                _root = new Node(kv);
                return true;
            }
            Node* parent = nullptr;
            Node* cur = _root;
            while(cur)
            {
                if(cur->_kv.first > kv.first)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_kv.first < kv.first)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    return false;
                }
            }
            cur = new Node(kv);
            if(parent->_kv.first > kv.first)
            {
                parent->_left = cur;
            }
            else if(parent->_kv.first < kv.first)
            {
                parent->_right = cur;
            }
            cur->_parent = parent;
            while(parent)
            {
                if(parent->_left == cur)
                {
                    parent->bf--;
                }
                else if(parent->_right == cur)
                {
                    parent->bf++;
                }
                if(parent->bf == 0)
                {
                    break;
                }
                else if(parent->bf == 1 || parent->bf == -1)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
                else if(parent->bf == 2 || parent->bf == -2)
                {
                    //调整
                    if(parent->bf == -2 && cur->bf == -1)
                    {
                        //右单旋
                        RotateR(parent);
                    }
                    else if(parent->bf == 2 && cur->bf == 1)
                    {
                        //左单旋
                        RotateL(parent);
                    }
                    else if(parent->bf == -2 && cur->bf == 1)
                    {
                        //左右双旋
                        RotateLR(parent);
                    }
                    else if(parent->bf == 2 && cur->bf == -1)
                    {
                        //右左双旋
                        RotateRL(parent);
                    }
                    else
                    {
                        assert(false);
                    }
                    break;
                }
                else
                {
                    assert(false);
                }
            }
            return true;
        }
        void InOrder()
        {
            _InOrder(_root);
        }
        size_t Hight()
        {
            return _Hight(_root);
        }
        size_t Size()
        {
            return _Size(_root);
        }
        bool IsAVLTree()
        {
            return _IsAVLTree(_root);
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while(cur)
            {
                if(cur->_kv.first > key)
                {
                    cur = cur->_left;
                }
                else if(cur->_kv.first < key)
                {
                    cur = cur->_right;
                }
                else if(cur->_kv.first == key)
                {
                    return cur;
                }
            }
            return nullptr;
        }
    protected:
        //右单旋
        void RotateR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            Node* ppNode = parent->_parent;
            subL->_right = parent;
            parent->_left = subLR;
            if(subLR)
                subLR->_parent = parent;
            parent->_parent = subL;
            if(parent == _root)
            {
                _root = subL;
                subL->_parent = nullptr;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subL;
                }
                else if(ppNode->_right == parent)
                {
                    ppNode->_right = subL;
                }
                subL->_parent = ppNode;
            }
            parent->bf = subL->bf = 0;
        }
        //左单旋
        void RotateL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            Node* ppNode = parent->_parent;
            parent->_right = subRL;
            subR->_left = parent;
            if(subRL)
                subRL->_parent = parent;
            parent->_parent = subR;
            if(parent == _root)
            {
                _root = subR;
                subR->_parent = nullptr;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subR;
                }
                else if(ppNode->_right == parent)
                {
                    ppNode->_right = subR;
                }
                subR->_parent = ppNode;
            }
            parent->bf = subR->bf = 0;
        }
        //左右双旋
        void RotateLR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            int bf = subLR->bf;
            RotateL(subL);
            RotateR(parent);
            if(bf == 0)
            {
                parent->bf = 0;
                subLR->bf = 0;
                subL->bf = 0;
            }
            else if(bf == 1)
            {
                // parent->bf = -1;
                // subLR->bf = 0;
                // subL->bf = 0;
                parent->bf = 0;
                subLR->bf = 0;
                subL->bf = -1;
            }
            else if(bf == -1)
            {
                // parent->bf = 0;
                // subLR->bf = 0;
                // subL->bf = 1;
                parent->bf = 1;
                subLR->bf = 0;
                subL->bf = 0;
            }
            else
            {
                assert(false);
            }
        }
        //右左双旋
        void RotateRL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            int bf = subRL->bf;
            RotateR(subR);
            RotateL(parent);
            if(bf == 0)
            {
                parent->bf = 0;
                subR->bf = 0;
                subRL->bf = 0;
            }
            else if(bf == 1)
            {
                // parent->bf = 0;
                // subR->bf = -1;
                // subRL->bf = 0;
                parent->bf = -1;
                subR->bf = 0;
                subRL->bf = 0;
            }
            else if(bf == -1)
            {
                // parent->bf = 1;
                // subR->bf = 0;
                // subRL->bf = 0;
                parent->bf = 0;
                subR->bf = 1;
                subRL->bf = 0;
            }
            else
            {
                assert(false);
            }
        }
        void _InOrder(Node* root)
        {
            if(root == nullptr) return;
            _InOrder(root->_left);
            cout << root->_kv.first << ":" << root->_kv.second << endl;
            _InOrder(root->_right);
        }
        size_t _Hight(Node* root)
        {
            if(root == nullptr) return 0;
            size_t leftHight = _Hight(root->_left);
            size_t rightHight = _Hight(root->_right);
            return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
        }
        size_t _Size(Node* root)
        {
            if(root == nullptr) return 0;
            return _Size(root->_left) + _Size(root->_right) + 1;
        }
        bool _IsAVLTree(Node* root)
        {
            if(root == nullptr) return true;
            size_t leftHight = _Hight(root->_left);
            size_t rightHight = _Hight(root->_right);
            int dicc = rightHight - leftHight;
            if(abs(dicc) >= 2)
            {
                cout << "高度差异常" << endl;
                return false;
            }
            if(dicc != root->bf)
            {
                cout << "平衡因子异常" << endl;
                cout << root->_kv.first << endl;
                return false;
            }
            return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}